var misc = require("./misc");

/**
 * Create a decision tree using ID3 algorithm.
 * 
 * @param dataSet an array of feature vector, with last element as class label.
 * @param labels optionally given the attribute names.
 * @return the decision tree object.
 */
function recursiveCreateDecisionTree(dataSet, attrNames) {
  var classList = dataSet.map(function (featVec) {
    return featVec[featVec.length - 1];
  });
  if (classList.every(function (it) { return it == classList[0]; })) { // pure?
    return classList[0];
  }
  if (dataSet[0].length == 1) {
    return misc.majorityCnt(classList);
  }
  var bestFeat = misc.calcInfoGains(dataSet).reduce(function (best, current) {
    if (best) {
      return best.infoGain > current.infoGain ? best : current;
    } else {
      return current;
    }
  });
  var label = attrNames[bestFeat.attr];
  attrNames.splice(bestFeat.attr, 1);
  return {
    label: label,
    branch: bestFeat.values.reduce(function (memo, current) {
      memo[current] = createDecisionTree(misc.splitDataSet(dataSet, bestFeat.attr, current), attrNames);
      return memo;
    }, {})
  };
}

/**
 * Create a decisition tree from a data set.
 * 
 * @param dataSet the set of feature vectors.
 * @return a decition tree model.
 */
function trainDecisionTree(dataSet) {
  var attrNames = [];
  for (var i=0; i<dataSet[0].length-1; i++) {
    attrNames[i] = i;
  }
  recursiveCreateDecisionTree(dataSet, attrNames);
}

exports.trainDecisionTree = trainDecisionTree;